{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Duplicates from Sorted List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteDuplicates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除排序链表中的重复元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个已排序的链表的头<meta charset=\"UTF-8\" />&nbsp;<code>head</code>&nbsp;，&nbsp;<em>删除所有重复的元素，使每个元素只出现一次</em>&nbsp;。返回 <em>已排序的链表</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/04/list1.jpg\" style=\"height: 160px; width: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,1,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/04/list2.jpg\" style=\"height: 123px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,1,2,3,3]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数目在范围 <code>[0, 300]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li>题目数据保证链表已经按升序 <strong>排列</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-duplicates-from-sorted-list](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-duplicates-from-sorted-list](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2]', '[1,1,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        cnts = defaultdict(int)\n",
    "        cur = head \n",
    "        while cur:\n",
    "            cnts[cur.val]+=1\n",
    "            cur = cur.next \n",
    "        cur1 = head \n",
    "        dummy = ListNode()\n",
    "        cur2 = dummy\n",
    "        while cur1:\n",
    "            if cnts[cur1.val] == 1:\n",
    "                cur2.next = cur1\n",
    "                cur2 = cur1 \n",
    "            cur1 = cur1.next \n",
    "        cur2.next = None \n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        duplicateDict = dict()\n",
    "\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            if cur.val in duplicateDict:\n",
    "                duplicateDict[cur.val] += 1\n",
    "            else:\n",
    "                duplicateDict[cur.val] = 1\n",
    "\n",
    "            cur = cur.next\n",
    "        \n",
    "        fast = head\n",
    "        slow = dummy\n",
    "        print(f'dict = {duplicateDict}')\n",
    "        \n",
    "        while fast:\n",
    "            if duplicateDict[fast.val] == 1:\n",
    "                slow.next = fast\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "            else:\n",
    "                # fast再遍历的时候，需要把所有的重复节点都跳过\n",
    "                while fast and duplicateDict[fast.val] > 1:\n",
    "                    fast = fast.next\n",
    "                # 要么fast 到最后\n",
    "                # 要么fast 到底一个不重复的node\n",
    "                slow.next = fast\n",
    "            \n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        d = defaultdict(int)\n",
    "        t = head \n",
    "        while t:\n",
    "            d[t.val] += 1\n",
    "            t = t.next\n",
    "        dummy = ListNode(0, head)\n",
    "        t = dummy\n",
    "        while t:\n",
    "            if t.next and d[t.next.val] > 1: t.next = t.next.next\n",
    "            else: t = t.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        b = ListNode(0, head)\n",
    "        d = {}\n",
    "        p = head\n",
    "        # 第一次遍历，查出重复的节点，\n",
    "        while p:\n",
    "            if p.val not in d:\n",
    "                d[p.val] = 1\n",
    "                b = b.next\n",
    "            else:\n",
    "                d[p.val] +=1\n",
    "                b.next = b = p.next\n",
    "            p = p.next\n",
    "        w = pr = ListNode(0, head)\n",
    "        \n",
    "        while head:\n",
    "            if d[head.val] > 1:\n",
    "                pr.next = head.next\n",
    "            else:\n",
    "                pr = pr.next\n",
    "            head = head.next\n",
    "        return w.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        p=head\n",
    "        q=dummy=ListNode()\n",
    "        while p:\n",
    "            if dic[p.val]==1:\n",
    "                q.next=p\n",
    "                q=q.next\n",
    "                p=p.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        q.next=None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = {}\n",
    "        p = head\n",
    "        while p:\n",
    "            if p.val not in count:\n",
    "                count[p.val] = 1\n",
    "            else:\n",
    "                count[p.val] += 1\n",
    "            p = p.next\n",
    "        dummy = ListNode(next = head)\n",
    "        \n",
    "        p = dummy\n",
    "        while p:\n",
    "            unique = p.next\n",
    "            while unique and count[unique.val] > 1:\n",
    "                unique = unique.next\n",
    "            p.next = unique\n",
    "            p = p.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=p=ListNode()\n",
    "        p.next=head\n",
    "        while p and p.next:\n",
    "            if dic[p.next.val]!=1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return q.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dic = defaultdict(int)\n",
    "        curr = head\n",
    "        while curr:\n",
    "            dic[curr.val] += 1\n",
    "            curr = curr.next\n",
    "        dummy = ListNode(0, head)\n",
    "        curr = dummy\n",
    "        while curr and curr.next:\n",
    "            while curr.next and dic[curr.next.val] >= 2:\n",
    "                curr.next = curr.next.next\n",
    "            curr = curr.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        p=head\n",
    "        cnt=defaultdict(int)\n",
    "        while p:\n",
    "            cnt[p.val]+=1\n",
    "            p=p.next\n",
    "        while head and cnt[head.val]>1:\n",
    "            head=head.next\n",
    "        if not head:\n",
    "            return head\n",
    "        p=head\n",
    "        while p.next:\n",
    "            if cnt[p.next.val]>1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        mp = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val not in mp:\n",
    "                mp[cur.val] = 1\n",
    "            else:\n",
    "                mp[cur.val] += 1\n",
    "            cur = cur.next\n",
    "        ans = ListNode(0, head)\n",
    "        cur = ans\n",
    "        while cur and cur.next:\n",
    "            if mp.get(cur.next.val) > 1:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)  # 哨兵节点\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val not in dup:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=p=ListNode()\n",
    "        p.next=head\n",
    "        while p and p.next:\n",
    "            if dic[p.next.val]!=1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return q.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = dict()\n",
    "        p = head\n",
    "\n",
    "        while p:\n",
    "            count[p.val] = count.get(p.val, 0) + 1\n",
    "            p = p.next \n",
    "        \n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head \n",
    "\n",
    "        p = dummy\n",
    "        while p:\n",
    "            unique = p.next\n",
    "\n",
    "            while unique and count[unique.val] > 1:\n",
    "                unique = unique.next\n",
    "            p.next = unique\n",
    "            p = p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = {}\n",
    "        p = head\n",
    "        while p:\n",
    "            count[p.val]  = count.get(p.val, 0) + 1\n",
    "            p = p.next\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "        while q:\n",
    "            if count[q.val] <= 1:\n",
    "                p.next = q\n",
    "                p = p.next\n",
    "            q = q.next\n",
    "        p.next = None\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        tab = set()\n",
    "        p = head\n",
    "        res = set()\n",
    "        while p:\n",
    "            if p.val in tab:\n",
    "                res.add(p.val)\n",
    "            else:\n",
    "                tab.add(p.val)\n",
    "            p = p.next\n",
    "        \n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "\n",
    "        while q:\n",
    "            if q.val not in res:\n",
    "                p.next = q\n",
    "                p = p.next\n",
    "            q = q.next\n",
    "        p.next = None\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val not in dup:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            else:\n",
    "                pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val in dup:\n",
    "                head = head.next\n",
    "            else:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "\n",
    "\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            else:\n",
    "                pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val in dup:\n",
    "                head = head.next\n",
    "            else:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "\n",
    "\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import collections\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        temp_head = head\n",
    "        nums = []\n",
    "        dummy_head = ListNode(0)\n",
    "        dummy_head.next = head\n",
    "        while temp_head:\n",
    "            nums.append(temp_head.val)\n",
    "            temp_head = temp_head.next\n",
    "        hash_list = collections.Counter(nums)\n",
    "        prev_head = dummy_head\n",
    "        while head:\n",
    "            if hash_list[head.val] != 1:              \n",
    "                prev_head.next = head.next\n",
    "                head = head.next\n",
    "            else:\n",
    "                prev_head = head\n",
    "                head = head.next\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fake = ListNode(val=-1)\n",
    "        fake.next = head\n",
    "\n",
    "        pre, cur = fake, head\n",
    "\n",
    "        while cur:\n",
    "            while cur.next and cur.val == cur.next.val:\n",
    "                cur = cur.next\n",
    "\n",
    "            if pre.next == cur:\n",
    "                pre = pre.next\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                pre.next = cur.next\n",
    "                cur = pre.next\n",
    "        return fake.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dm = ListNode(0)\n",
    "        cur = dm\n",
    "        while head:\n",
    "            if not head.next or head.next.val != head.val:\n",
    "                cur.next = head\n",
    "                cur = cur.next\n",
    "                head = head.next\n",
    "                cur.next = None\n",
    "            else:\n",
    "                while head and head.next and head.next.val == head.val:\n",
    "                    head = head.next\n",
    "                if head:\n",
    "                    head = head.next\n",
    "        return dm.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head==None or head.next==None:#如果是空链表，或者只有一个节点的链表，直接返回\n",
    "            return head\n",
    "        \n",
    "        #先处理头部，让第一个数字不是重复的\n",
    "        while head!=None and head.next!=None and head.val==head.next.val:\n",
    "            num=head.val\n",
    "            while head!=None and head.val==num:\n",
    "                head=head.next\n",
    "        \n",
    "        if head==None or head.next==None or head.next.next==None:#如果变成空链表，或者只有一个、两个节点的链表，直接返回\n",
    "            return head\n",
    "        \n",
    "        ptr=head.next#指向当前数字\n",
    "        preptr=head#指向上一个不同的数字\n",
    "\n",
    "        while ptr!=None and ptr.next!=None:\n",
    "            num=ptr.val\n",
    "            if ptr.next.val==num:\n",
    "                while ptr!=None and ptr.val==num:\n",
    "                    preptr.next=ptr.next\n",
    "                    ptr=ptr.next\n",
    "            else:\n",
    "                preptr=ptr\n",
    "                ptr=ptr.next\n",
    "                \n",
    "        return head           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        nh = ListNode(0)\n",
    "        node = nh.next = head\n",
    "        pre = nh\n",
    "        while node:\n",
    "            if node.next and node.val == node.next.val:\n",
    "                while node.next and node.val == node.next.val:\n",
    "                    node = node.next\n",
    "                pre.next = node.next\n",
    "                node = node.next\n",
    "            else:\n",
    "                pre = pre.next\n",
    "                node = node.next\n",
    "        return nh.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "            \n",
    "        start=ListNode(0)\n",
    "        start.next=head\n",
    "        p=start\n",
    "        cur=start.next\n",
    "        \n",
    "        while cur!=None:\n",
    "            while cur.next and cur.next.val==p.next.val:\n",
    "                cur=cur.next\n",
    "            if p.next==cur:\n",
    "                p=p.next\n",
    "            else:\n",
    "                p.next=cur.next\n",
    "            cur=cur.next\n",
    "        return start.next\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        if(head==None or head.next==None):return head\n",
    "        N=ListNode(0)\n",
    "        N.next=head\n",
    "        head=N\n",
    "        while N!=None and N.next!=None:\n",
    "            M=N.next\n",
    "            i=0\n",
    "            while M!=None  and M.val==N.next.val:\n",
    "                M=M.next\n",
    "                i=i+1\n",
    "            print(N.val,i)\n",
    "            if i>=2:N.next=M\n",
    "            else:N=N.next\n",
    "            \n",
    "        \n",
    "        return head.next\n",
    "                \n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        h = ListNode(0)\n",
    "        h.next = head\n",
    "        p,q = h,head\n",
    "        count = 1\n",
    "        while q :\n",
    "            while q.next and q.next.val == q.val:\n",
    "                count += 1\n",
    "                print(count)\n",
    "                q = q.next\n",
    "            if count == 1:\n",
    "                p.next = q \n",
    "                p = q\n",
    "            q = q.next\n",
    "            count = 1\n",
    "        p.next = q\n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        indicator = collections.defaultdict()\n",
    "        pointer = head\n",
    "        while pointer is not None:\n",
    "            k = pointer.val\n",
    "            if k not in indicator.keys():\n",
    "                indicator[k] = 1\n",
    "            else:\n",
    "                indicator[k] = indicator.get(k)+1\n",
    "            pointer = pointer.next\n",
    "        list_index = []\n",
    "        for k in indicator.keys():\n",
    "            if indicator.get(k) > 1:\n",
    "                list_index.append(k)\n",
    "\n",
    "        add_node = ListNode('add')\n",
    "        add_node.next = head\n",
    "        pointer = add_node\n",
    "        cur = pointer.next\n",
    "        while cur is not None:\n",
    "            k = cur.val\n",
    "            if  k in list_index:\n",
    "                if cur.next is not None:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    pointer.next = cur.next\n",
    "                    break\n",
    "            else:\n",
    "                pointer.next = cur\n",
    "                pointer = pointer.next\n",
    "                if cur.next is not None:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return add_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        thead = ListNode(0)\n",
    "        thead.next = head\n",
    "        pre, cur = None, thead\n",
    "        while cur:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            while cur and cur.next and cur.next.val == cur.val:\n",
    "                t = cur.val\n",
    "                while cur and cur.val == t:\n",
    "                    cur = cur.next\n",
    "                pre.next = cur\n",
    "\n",
    "        return thead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        if head.next and (head.val == head.next.val):\n",
    "            while (head.next != None) and (head.val == head.next.val):\n",
    "                head = head.next\n",
    "            return self.deleteDuplicates(head.next)\n",
    "        else:\n",
    "            head.next = self.deleteDuplicates(head.next)\n",
    "        return head\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        preptr = dummy\n",
    "        while preptr:\n",
    "            if not preptr.next:\n",
    "                return dummy.next\n",
    "            val = preptr.next.val\n",
    "            nextptr = preptr.next.next\n",
    "            if nextptr and nextptr.val == val:\n",
    "                while nextptr and nextptr.val == val:\n",
    "                    nextptr = nextptr.next\n",
    "                preptr.next = nextptr\n",
    "            else:\n",
    "                preptr = preptr.next\n",
    "        return dummy.next  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:#感谢各位的更好思路或改进办法\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        thead = ListNode('a')\n",
    "        thead.next = head\n",
    "        pre,cur = None,thead\n",
    "        while cur:\n",
    "            pre=cur\n",
    "            cur=cur.next\n",
    "            while cur and cur.next and cur.next.val == cur.val:\n",
    "                t=cur.val\n",
    "                while cur and cur.val==t:\n",
    "                    cur=cur.next\n",
    "            pre.next=cur\n",
    "        return thead.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        dummy=ListNode(-1)\n",
    "        dummy.next=head\n",
    "        p=dummy\n",
    "\n",
    "        while p.next:\n",
    "            q=p.next.next\n",
    "            while q and q.val==p.next.val:\n",
    "                q=q.next\n",
    "            if p.next.next==q:\n",
    "                p=p.next\n",
    "            else:\n",
    "                p.next=q\n",
    "        \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        pre = None\n",
    "        while head:\n",
    "            # 如果当前节点与下一个节点值相同，指针向后移动\n",
    "            while head.next and head.val == head.next.val:\n",
    "                pre = head.val\n",
    "                head = head.next\n",
    "            # 如果当前节点值与前后节点值均不相同，则将当前节点添加到新链表中\n",
    "            if head.val != pre:\n",
    "                cur.next = head\n",
    "                cur = cur.next\n",
    "            head = head.next\n",
    "        # 最后将新链表最后指针的下一个位置指向空\n",
    "        cur.next = None\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        pre = dummy\n",
    "\n",
    "        while pre.next and pre.next.next:\n",
    "            if pre.next.val == pre.next.next.val:\n",
    "                label = pre.next.val\n",
    "                while pre.next and pre.next.val == label:\n",
    "                    pre.next = pre.next.next\n",
    "\n",
    "            else:\n",
    "                pre = pre.next\n",
    "        \n",
    "        return dummy.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        tmp = head\n",
    "        if tmp is None:\n",
    "            return  head\n",
    "        last_val = None\n",
    "        last_node = None\n",
    "        flag = False\n",
    "        left = None\n",
    "        ret_head = None\n",
    "        while(tmp):\n",
    "            if tmp.val != last_val:\n",
    "                if not flag and last_node:\n",
    "                    if not left:\n",
    "                        left = last_node\n",
    "                        ret_head = left\n",
    "                    else:\n",
    "                        left.next = last_node\n",
    "                        left = last_node\n",
    "                last_val = tmp.val\n",
    "                last_node = tmp\n",
    "                flag = False\n",
    "                tmp = tmp.next\n",
    "            else:\n",
    "                flag = True\n",
    "                tmp = tmp.next\n",
    "        \n",
    "        if not flag:\n",
    "            if not left:\n",
    "                return last_node\n",
    "            left.next = last_node\n",
    "            left = left.next\n",
    "            left.next = None\n",
    "        else:\n",
    "            if not left:\n",
    "                return None\n",
    "            left.next = None\n",
    "        \n",
    "        return ret_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        self.duplicate = None\n",
    "        \n",
    "        def delete_num(head):\n",
    "            if  not head.next:\n",
    "                return head\n",
    "            next_node = delete_num(head.next)\n",
    "            if next_node is not None and next_node.val == head.val:\n",
    "                self.duplicate = head.val\n",
    "                head = next_node.next\n",
    "            elif head.val == self.duplicate:\n",
    "                head = next_node\n",
    "            else:\n",
    "                head.next = next_node\n",
    "            return head\n",
    "        return delete_num(head)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        l1 = []\n",
    "        ln1 = ListNode(0)\n",
    "        while head:\n",
    "            l1.append(head.val)\n",
    "            head = head.next\n",
    "        n = len(l1)-1\n",
    "        print(l1)\n",
    "        for i in range(n,-1,-1):\n",
    "            if l1.count(l1[i]) == 1:\n",
    "                ln1.val = l1[i]\n",
    "                ln1.next = copy.deepcopy(ln1)\n",
    "            print(i)\n",
    "        return ln1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        record = defaultdict(int)\n",
    "        \n",
    "        dummyhead = ListNode(0)\n",
    "        dummyhead.next = head\n",
    "        cur = head\n",
    "        \n",
    "        while cur != None:\n",
    "            record[cur.val] += 1\n",
    "            cur = cur.next\n",
    "        \n",
    "        \n",
    "        pre = dummyhead\n",
    "        cur = head   # 此时要重新把cur指向head，上面一次遍历，cur已经指向了链表尾部的None\n",
    "        \n",
    "        while cur != None:\n",
    "           \n",
    "            if record[cur.val] > 1:\n",
    "                print( record[cur.val] )\n",
    "                next = cur.next\n",
    "                \n",
    "                delnode = cur\n",
    "                pre.next = next\n",
    "                cur = next\n",
    "                delnode.next = None\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        \n",
    "        \n",
    "        retnode = dummyhead.next\n",
    "        dummyhead.next = None\n",
    "        \n",
    "        return retnode\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        ans = ListNode(0,head)\n",
    "        cur = ans\n",
    "\n",
    "\n",
    "        while cur.next and cur.next.next:\n",
    "\n",
    "            if cur.next.val == cur.next.next.val:\n",
    "                x = cur.next.val\n",
    "                while cur.next and cur.next.val==x:\n",
    "                    cur.next = cur.next.next\n",
    "                \n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return ans.next\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        to_list = []\n",
    "\n",
    "\n",
    "        while head:\n",
    "            to_list.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        dic = {}\n",
    "        for i in to_list:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        \n",
    "        new_list = []\n",
    "        for key in dic:\n",
    "            if dic[key] == 1:\n",
    "                new_list.append(key)\n",
    "        \n",
    "        if len(new_list) == 0:\n",
    "            return \n",
    "        \n",
    "        new_list = sorted(new_list)\n",
    "        \n",
    "        newhead = ListNode(new_list[0])\n",
    "        curr = newhead\n",
    "\n",
    "        for i in range(1, len(new_list)):\n",
    "            curr.next = ListNode(new_list[i])\n",
    "            curr = curr.next\n",
    "          \n",
    "        \n",
    "        return newhead\n",
    "            \n",
    "        \n",
    "      \n",
    "        \n",
    "       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        cur = dummy\n",
    "        while cur.next and cur.next.next:\n",
    "            val = cur.next.val\n",
    "            if cur.next.next.val == val:\n",
    "                while cur.next and cur.next.val == val:\n",
    "                    cur.next =cur.next.next\n",
    "\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head \n",
    "        dummy = ListNode(next=head)\n",
    "        cur = dummy \n",
    "        while cur.next and cur.next.next:\n",
    "            if cur.next.val == cur.next.next.val:\n",
    "                x = cur.next.val \n",
    "                while cur.next and cur.next.val == x:\n",
    "                    cur.next = cur.next.next \n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _rec(self, prev_ndup: ListNode, prev: ListNode, the: ListNode, dup: int):\n",
    "        if the is None:\n",
    "            # !!\n",
    "            if dup == 0:\n",
    "                prev_ndup.next = prev\n",
    "            else:\n",
    "                prev_ndup.next = None\n",
    "            return\n",
    "        \n",
    "        if prev.val == the.val:\n",
    "            self._rec(prev_ndup=prev_ndup, prev=the, the=the.next, dup=dup+1)\n",
    "        else:\n",
    "            if dup == 0:\n",
    "                prev_ndup.next = prev  # !\n",
    "                self._rec(prev_ndup=prev_ndup.next, prev=the, the=the.next, dup=0)\n",
    "            else:\n",
    "                self._rec(prev_ndup=prev_ndup, prev=the, the=the.next, dup=0)\n",
    "        \n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "            \n",
    "        dummy_head = ListNode(-999, head) # !\n",
    "        self._rec(dummy_head, dummy_head, dummy_head.next, 0)\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        ans=ListNode(None)\n",
    "        ans.next=head\n",
    "        pre=ans\n",
    "        pre.next=None\n",
    "        \n",
    "        num=1\n",
    "        last=head.val\n",
    "        slow=head\n",
    "        head=head\n",
    "\n",
    "        while head:\n",
    "            while head and head.val==last:\n",
    "                slow=head\n",
    "                head=head.next\n",
    "                num+=1\n",
    "            print(num)\n",
    "            if num==2:\n",
    "                pre.next=slow\n",
    "                pre=slow\n",
    "            else:\n",
    "                if head==None:\n",
    "                    pre.next=None\n",
    "\n",
    "            head=slow.next\n",
    "            if head:\n",
    "                last=head.val\n",
    "            num=1\n",
    "        \n",
    "\n",
    "        return ans.next\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        # while head:\n",
    "        #     if head.val==last:\n",
    "        #         pre.next=head.next\n",
    "        #         head=head.next\n",
    "        #     else:\n",
    "        #         last=head.val\n",
    "        #         pre=head\n",
    "        #         head=head.next\n",
    "                \n",
    "        # return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if not cur or not cur.next:\n",
    "                return cur\n",
    "            if cur.val != cur.next.val:\n",
    "                cur.next = self.deleteDuplicates(cur.next)\n",
    "            else:\n",
    "                move = cur.next\n",
    "                while move and move.val == cur.val:\n",
    "                    move = move.next\n",
    "                return self.deleteDuplicates(move)\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        cur=dummy\n",
    "        while cur.next and cur.next.next:\n",
    "            if cur.next.val==cur.next.next.val:\n",
    "                val=cur.next.val\n",
    "                while cur.next and cur.next.val==val:\n",
    "                    cur.next=cur.next.next\n",
    "            else:\n",
    "                cur=cur.next\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next=head)\n",
    "        cur = dummy\n",
    "        while cur.next and cur.next.next:\n",
    "            val = cur.next.val\n",
    "            if cur.next.next.val == val:\n",
    "                while cur.next and cur.next.val ==val:  #这里的操作相当于把next删掉，不要想成一下子跳过多少个，一个一个来\n",
    "                    cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy.next\n",
    "                \n",
    "        \n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        current = head\n",
    "        if head == None:\n",
    "            return head\n",
    "        while current.next:\n",
    "            if current.val == current.next.val:\n",
    "                current.next = current.next.next\n",
    "            else:\n",
    "                current = current.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return None\n",
    "        pre,hthis = head,head.next\n",
    "        while hthis:\n",
    "            if pre.val == hthis.val:\n",
    "                pre.next = hthis.next\n",
    "                hthis = hthis.next \n",
    "            else:\n",
    "                pre = pre.next\n",
    "                hthis = hthis.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        dummy = ListNode(head.val - 1)\n",
    "        cur = dummy\n",
    "        while head:\n",
    "            if head.val != cur.val:\n",
    "                cur.next = head\n",
    "                cur = cur.next\n",
    "            head = head.next\n",
    "        cur.next = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: 'ListNode') -> 'ListNode':\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        head.next = self.deleteDuplicates(head.next)\n",
    "        return head.next if head.val == head.next.val else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        list_ = []\n",
    "        while head != None:\n",
    "            if head.val not in list_:\n",
    "                list_ += [head.val]\n",
    "            head = head.next\n",
    "        return list_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return []\n",
    "        pre_node = head\n",
    "        node = pre_node.next\n",
    "        while node != None:\n",
    "            if node.val == pre_node.val:\n",
    "                pre_node.next = node.next\n",
    "            else:\n",
    "                pre_node = node\n",
    "            node = node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return []\n",
    "        pre_node = head\n",
    "        node = pre_node.next\n",
    "        while node != None:\n",
    "            if node.val == pre_node.val:\n",
    "                pre_node.next = node.next\n",
    "            else:\n",
    "                pre_node = node\n",
    "            node = node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return\n",
    "        if head.next == None:\n",
    "            return head\n",
    "        p = head\n",
    "        q = head.next\n",
    "        while q:\n",
    "            if p and q:\n",
    "                print(p.val, q.val)\n",
    "            if q.val == p.val:\n",
    "                p.next = q.next\n",
    "                q = q.next\n",
    "            else:\n",
    "                p = p.next\n",
    "                q = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return None\n",
    "        has = []\n",
    "        r = temp = ListNode(0)\n",
    "        while head != None:\n",
    "            print(head.val)\n",
    "            if head.val not in has:\n",
    "                has.append(head.val)\n",
    "                temp.next = ListNode(head.val)\n",
    "                temp = temp.next\n",
    "            \n",
    "            head = head.next\n",
    "            \n",
    "        return r.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        p1 = ListNode(None)\n",
    "        p1.next = head \n",
    "        while p1.next is not None:\n",
    "            if p1.val == p1.next.val:\n",
    "                if p1.next.next is None:\n",
    "                    p1.next = None\n",
    "                else:\n",
    "                    p1.next = p1.next.next\n",
    "            else:\n",
    "                p1 = p1.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head \n",
    "        cur = head.next \n",
    "        mark = head.val\n",
    "        start = head  \n",
    "        while cur:\n",
    "            if cur.val == mark:\n",
    "                start.next = cur.next \n",
    "            else:\n",
    "                start = cur\n",
    "                mark = start.val  \n",
    "            cur = cur.next \n",
    "        return head \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def deleteDuplicates(self, head):\n",
    "        if not head:\n",
    "            return head\n",
    "        temp=head\n",
    "        while((temp and temp.next)!=None):\n",
    "            if temp.val==temp.next.val:\n",
    "                temp.next=temp.next.next\n",
    "            else:\n",
    "                temp=temp.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        ans = head\n",
    "        while head != None:\n",
    "            if head.next != None and head.next.val == head.val:\n",
    "                head.next = head.next.next\n",
    "            else:\n",
    "                head = head.next\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        pre = head\n",
    "        current = head.next\n",
    "        while current:\n",
    "            if current.val == pre.val:\n",
    "                pre.next = current.next\n",
    "                current = pre.next\n",
    "            else:\n",
    "                pre = pre.next\n",
    "                current = current.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        first_head = head\n",
    "        while head is not None and head.next is not None:\n",
    "            if head.val == head.next.val:\n",
    "                head.next = head.next.next\n",
    "            else:\n",
    "                head = head.next\n",
    "\n",
    "        return first_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        while head.next is not None and head.val == head.next.val:\n",
    "            head = head.next\n",
    "        if head.next is None:\n",
    "            return head\n",
    "        \n",
    "        previous = head\n",
    "        node = previous.next\n",
    "        while node.next is not None:\n",
    "            if node.val == node.next.val:\n",
    "                node = node.next\n",
    "            else:\n",
    "                previous.next = node\n",
    "                previous = node\n",
    "                node = node.next\n",
    "        previous.next = node\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        tmp = head\n",
    "        if tmp is None:\n",
    "            return  head\n",
    "        last_val = None\n",
    "        last_node = None\n",
    "        while(tmp):\n",
    "            if tmp.val != last_val:\n",
    "                last_val = tmp.val\n",
    "                last_node = tmp\n",
    "                tmp = tmp.next\n",
    "            else:\n",
    "                last_node.next = tmp.next\n",
    "                tmp = tmp.next\n",
    "\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return\n",
    "\n",
    "        pre = head\n",
    "        cur = pre.next\n",
    "\n",
    "        while not cur is None:\n",
    "            if pre.val == cur.val:\n",
    "\n",
    "                tmp = cur.next  ##找到第一个不相等\n",
    "                while not tmp is None:\n",
    "                    if tmp.val == pre.val:\n",
    "                        tmp = tmp.next\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                pre.next = tmp\n",
    "                cur = tmp\n",
    "                \n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        s = []\n",
    "\n",
    "        while head:\n",
    "            print(head.val)\n",
    "            if head.val not in s:\n",
    "                s.append(head.val)\n",
    "                head = head.next\n",
    "            else:\n",
    "                head = head.next\n",
    "\n",
    "        for item in s:\n",
    "            if item == s[0]:\n",
    "                l = ListNode(item)\n",
    "                g = l\n",
    "            else:\n",
    "                k = ListNode(item)\n",
    "                g.next = k\n",
    "                g = g.next\n",
    "        return l\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        N = deepcopy(head)\n",
    "        newlist = ListNode(0)\n",
    "        newlist.next = head \n",
    "        while head != None and head.next != None:\n",
    "        \n",
    "            if head.val == head.next.val:\n",
    "                head.next = head.next.next\n",
    "            else:\n",
    "                head = head.next\n",
    "        return newlist.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "def delete_duplicate_linked_node(root):\n",
    "    if not root:\n",
    "        return root\n",
    "    prev = root\n",
    "    node = root.next\n",
    "    while node:\n",
    "        if node.val != prev.val:\n",
    "            prev = prev.next\n",
    "            prev.val = node.val\n",
    "        node = node.next\n",
    "    prev.next = None\n",
    "    return root\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: ListNode) -> ListNode:\n",
    "        return delete_duplicate_linked_node(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast:\n",
    "            if slow.val != fast.val:\n",
    "                slow.next = fast\n",
    "                slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        slow.next = None\n",
    "\n",
    "        return head\n",
    "\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        # slow = head\n",
    "        # fast = head.next\n",
    "        # pre_fast = head\n",
    "\n",
    "        # while fast:\n",
    "        #     if slow.val != fast.val:\n",
    "        #         slow = slow.next\n",
    "        #         pre_fast = fast\n",
    "        #         fast = fast.next\n",
    "        #     else:\n",
    "        #         pre_fast.next = fast.next\n",
    "        #         fast = fast.next\n",
    "\n",
    "        # return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # if head is None:\n",
    "        #     return None\n",
    "        # cur = head\n",
    "        # while cur.next:\n",
    "        #     if cur.next.val == cur.val:\n",
    "        #         cur.next = cur.next.next\n",
    "        #     else:\n",
    "        #         cur = cur.next\n",
    "        # return head\n",
    "        if not head:\n",
    "            return None\n",
    "        cur=head\n",
    "        while cur.next:\n",
    "            if cur.val==cur.next.val:\n",
    "                cur.next=cur.next.next\n",
    "            else:\n",
    "                cur=cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast, slow = head, head\n",
    "        while fast:\n",
    "            if fast.val == slow.val:\n",
    "                slow.next = fast.next\n",
    "            else:\n",
    "                slow = slow.next\n",
    "            fast = fast.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "class ListNode:\r\n",
    "    def __init__(self, val=0, next=None):\r\n",
    "        self.val = val\r\n",
    "        self.next = next\r\n",
    "class Solution:\r\n",
    "    def deleteDuplicates(self, head):\r\n",
    "        result = ListNode('')\r\n",
    "        last_node = result\r\n",
    "\r\n",
    "        while head:\r\n",
    "            # if not result.next:\r\n",
    "            #     result.next.val = head.val\r\n",
    "            #     result.next.next = None\r\n",
    "            #     continue\r\n",
    "            # if head.val == 0:\r\n",
    "            #     last_node.next = head\r\n",
    "            #     last_node = \r\n",
    "\r\n",
    "            # 下一个节点的值与上一个节点的值不同, 更新最后一个节点为当前节点\r\n",
    "            if head.val != last_node.val:\r\n",
    "                last_node.next = head\r\n",
    "                last_node = last_node.next\r\n",
    "                head = head.next\r\n",
    "\r\n",
    "            # 下一个节点的值与上一个节点的值相同, 跳过\r\n",
    "            else:\r\n",
    "                head = head.next\r\n",
    "                last_node.next = head\r\n",
    "\r\n",
    "        \r\n",
    "        last_node.next = None\r\n",
    "\r\n",
    "        return result.next\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # print(head.val)\n",
    "        node = head\n",
    "        last_node = ListNode(-101, head)\n",
    "        \n",
    "        print(head)\n",
    "        print(node)\n",
    "        while node:\n",
    "            if node.val == last_node.val:\n",
    "                last_node.next = node.next\n",
    "                node = node.next\n",
    "            else:\n",
    "                last_node = node\n",
    "                node = node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        while p and p.next:\n",
    "            if p.val == p.next.val:\n",
    "                p.next = p.next.next\n",
    "                continue\n",
    "            p = p.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p = head\n",
    "        while p and p.next:\n",
    "            if p.val == p.next.val: p.next = p.next.next\n",
    "            else: p = p.next\n",
    "        return head \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        cur = head \n",
    "        while cur.next:\n",
    "            if cur.val == cur.next.val:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return head"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
